﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 正则表达式匹配
{
    class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            //Console.WriteLine(solution.Reverse(test));
            Console.WriteLine("false "+  solution.IsMatch("aa", "a"));
            Console.WriteLine("true " + solution.IsMatch("aa", "a*"));
            Console.WriteLine("true " + solution.IsMatch("ab", ".*"));
            Console.WriteLine("true " + solution.IsMatch("aab", "c*a*b"));
            Console.WriteLine("false " + solution.IsMatch("mississippi", "mis*is*p*."));
            Console.WriteLine("true " + solution.IsMatch("mississippi", "mis*is*ip*."));
            Console.WriteLine("true " + solution.IsMatch("aaa", "ab*ac*a"));
            Console.WriteLine("false " + solution.IsMatch("aaa", ".a"));
            Console.WriteLine("false " + solution.IsMatch("aaa", "ab*a"));
            Console.ReadLine();
        }
    }
    public class Solution
    {

        public bool IsMatch(string s, string p)
        {
            //出口，EXIT
            if (string.IsNullOrEmpty(p)) 
                return string.IsNullOrEmpty(s); //Exit

            bool first_match = (
               !string.IsNullOrEmpty(s) &&
               (p[0] == s[0] || p[0] == '.')
           );

            if (p.Length >= 2 && p[1] == '*')
            {
                return (IsMatch(s, p.Substring(2)) ||       // A
                (first_match && IsMatch(s.Substring(1), p))); //B
            }
            else
            {
                return first_match && IsMatch(s.Substring(1), p.Substring(1)); // C
            }
            
        }
        public bool IsMatch1(string s, string p)
        {
            bool result = false;
            int length1 = s.Length;
            int length2 = p.Length;
            if (length1 != length2)
            {
                if (!p.Contains('*') && !p.Contains('.'))
                {
                    return false;
                }
            }
            if (length1 == 0 || length2 == 0)
            {
                return false;
            }
            num = 1;
            result = Match(s, p);
            return result;
        }
        string last;
        int num;
        private bool Match(string s, string p)
        {
            if (s.Length == 0)
            {
                return true;
            }
            if (p.Length == 0)
            {
                return false;
            }
            if(s.Length - 2 < 0)
            {
                last = "";
            }
            else
            {
                last = s[s.Length-2].ToString();
            }
  
            if (s[s.Length - 1] == p[p.Length - 1])
            {
                return Match(s.Substring(0, s.Length - 1), p.Substring(0, p.Length - 1));
            }
            else
            {
                if (p[p.Length - 1] == '.')
                {
                    return Match(s.Substring(0, s.Length - 1), p.Substring(0, p.Length - 1));
                }
                else if (p[p.Length - 1] == '*')
                {
                    if (s[s.Length - 1].ToString() == last)
                    {
                        num++;
                        return Match(s.Substring(0, s.Length - 1), p.Substring(0, p.Length));
                    }
                    int a = num;
                    num = 1;
                    //return Match(s.Substring(0, s.Length - 1), p.Substring(0, p.Length - a<0?0: p.Length - a));
                    return Match(s.Substring(0, s.Length - 1), p.Substring(0,p.Length - a));
                }
                else
                {
                    return false;
                }
            }
        }
    }
}
